#include "Graph.h"
#include <iostream>
#include <cstdlib>
#include <ctime>

struct Edge_List
{
    int vertex;
    int adjvex; // adjacent vertex
    double weight;
    Edge_List( int vertex, int adjvex, const double & weight ) 
        : vertex{ vertex }, adjvex{ adjvex }, weight{ weight } { }
};


double* BF(Graph &g, int n) // 计算从n出发的最短路径，认为g以邻接矩阵存储
{
    int numV = g.getNumV();
    int numE = g.getNumE();
    Edge_List **list;
    list = new Edge_List* [numE];
    int itor = 0;
    //将邻接矩阵转为邻接表
    if(g.getDirected()) // 有向图整个矩阵全部遍历一遍
    {
        for(int i=0; i<numV; i++)
            for( int j=0; j<numV; j++ )
            {
                if (g.getWeight(i,j)!=INF)
                {
                    list[itor] = new Edge_List(i, j, g.getWeight(i,j));
                    itor++;
                }
            }
    }
    else // 无向图遍历矩阵上三角
    {
        for(int i=0; i<numV; i++)
            for( int j=i+1; j<numV; j++ )
            {
                if (g.getWeight(i,j)!=INF)
                {
                    list[itor] = new Edge_List(i, j, g.getWeight(i,j));
                    itor++;
                }
            }
    }
    
    double* d = new double[numV]; // 存放distance的数组
    for (int i=0; i<numV; i++)
        d[i] = INF;
    d[n] = 0;
    for (int i=0; i<numV; i++)
    {
        for (int j=0; j<numE; j++)
        {
            if(g.getDirected())
            {
                int u = list[j]->vertex;
                int v = list[j]->adjvex;
                if ( d[v]>(d[u]+list[j]->weight) )
                    d[v] = d[u]+list[j]->weight;
            }
            else
            {
                int u = list[j]->vertex;
                int v = list[j]->adjvex;
                if ( d[v]>(d[u]+list[j]->weight) )
                    d[v] = d[u]+list[j]->weight;
                u = list[j]->adjvex;
                v = list[j]->vertex;
                if ( d[v]>(d[u]+list[j]->weight) )
                    d[v] = d[u]+list[j]->weight;
            }
            
        }
    }
    for (int j=0; j<numE; j++)
    {
        if(g.getDirected())
        {
            int u = list[j]->vertex;
            int v = list[j]->adjvex;
            if ( d[v]>(d[u]+list[j]->weight) )
            {
                cout << "存在负边环" << endl;
                for( int i=0; i<numE; i++ )
                    delete[] list[i];
                delete[] list;
                return d;
            }
        }
        else
        {
            int u = list[j]->vertex;
            int v = list[j]->adjvex;
            if ( d[v]>(d[u]+list[j]->weight) )
            {
                cout << "存在负边环" << endl;
                for( int i=0; i<numE; i++ )
                    delete[] list[i];
                delete[] list;
                return d;
            }
            u = list[j]->adjvex;
            v = list[j]->vertex;
            if (d[v]>(d[u]+list[j]->weight))
            {
                cout << "存在负边环" << endl;
                for( int i=0; i<numE; i++ )
                    delete[] list[i];
                delete[] list;
                return d;
            }
        }
        
    }
    for( int i=0; i<numE; i++ )
        delete[] list[i];
    delete[] list;
    return d;
}

int main()
{
    int numV = 5;
    int numE = 8;
    int flag = 1;
    bool isWeighted = true;
    bool isDirected = false;
    int edge = 0;
    Graph g(numV, numE, flag, isWeighted, isDirected);
    srand(time(0));
    while(g.getIterator()<numE)//生成含有numE条边的图
    {
        int i = rand() % numV;
        int j = rand() % numV;
        if ( g.getWeight(i, j)==INF && i!=j)
            g.setEdgeWeight(i, j, rand()%99+1);
    }
    g.listEdges( );
    g.listVertexes( );

    cout << "从0出发最小距离: " << endl;
    double* d = BF(g, 0);
    for(int i; i<numV; i++)
    {
        if(d[i]==INF)
            cout << "INF ";
        else 
            cout << d[i] << " ";
    }
    cout << endl;
    delete d;

    cout << "从1出发最小距离: " << endl;
    d = BF(g, 1);
    for(int i; i<numV; i++)
    {
        if(d[i]==INF)
            cout << "INF ";
        else 
            cout << d[i] << " ";
    }
    cout << endl;
    delete d;
    cout << "-----------------------" <<endl;
    
    cout << "节点数：1000，边数：1000" << endl;
    numV = 1000;
    numE = 1000;
    edge = 0;
    Graph g1(numV, numE, flag, isWeighted, isDirected);
    while(g1.getIterator()<numE)//生成含有numE条边的图
    {
        int i = rand() % numV;
        int j = rand() % numV;
        if ( g1.getWeight(i, j)==INF && i!=j)
            g1.setEdgeWeight(i, j, rand()%99+1);
    }
    clock_t start,stop;
    start = clock();
    d = BF(g1, 0);
    stop = clock();
    cout << "The average time: " << double(stop-start)/double(1000) << "ms" << endl;
    delete d;

    cout << "节点数：1000，边数：2000" << endl;
    numV = 1000;
    numE = 2000;
    edge = 0;
    Graph g2(numV, numE, flag, isWeighted, isDirected);
    while(g2.getIterator()<numE)//生成含有numE条边的图
    {
        int i = rand() % numV;
        int j = rand() % numV;
        if ( g2.getWeight(i, j)==INF && i!=j)
            g2.setEdgeWeight(i, j, rand()%99+1);
    }
    start = clock();
    d = BF(g2, 0);
    stop = clock();
    cout << "The average time: " << double(stop-start)/double(1000) << "ms" << endl;
    delete d;


    cout << "节点数：1000，边数：4000" << endl;
    numV = 1000;
    numE = 4000;
    edge = 0;
    Graph g3(numV, numE, flag, isWeighted, isDirected);
    while(g3.getIterator()<numE)//生成含有numE条边的图
    {
        int i = rand() % numV;
        int j = rand() % numV;
        if ( g3.getWeight(i, j)==INF && i!=j)
            g3.setEdgeWeight(i, j, rand()%99+1);
    }
    start = clock();
    d = BF(g3, 0);
    stop = clock();
    cout << "The average time: " << double(stop-start)/double(1000) << "ms" << endl;
    delete d;

    cout << "节点数：2000，边数：1000" << endl;
    numV = 2000;
    numE = 1000;
    edge = 0;
    Graph g4(numV, numE, flag, isWeighted, isDirected);
    while(g4.getIterator()<numE)//生成含有numE条边的图
    {
        int i = rand() % numV;
        int j = rand() % numV;
        if ( g4.getWeight(i, j)==INF && i!=j)
            g4.setEdgeWeight(i, j, rand()%99+1);
    }
    start = clock();
    d = BF(g4, 0);
    stop = clock();
    cout << "The average time: " << double(stop-start)/double(1000) << "ms" << endl;
    delete d;

    cout << "节点数：10000，边数：1000" << endl;
    numV = 10000;
    numE = 1000;
    edge = 0;
    Graph g5(numV, numE, flag, isWeighted, isDirected);
    while(g5.getIterator()<numE)//生成含有numE条边的图
    {
        int i = rand() % numV;
        int j = rand() % numV;
        if ( g5.getWeight(i, j)==INF && i!=j)
            g5.setEdgeWeight(i, j, rand()%99+1);
    }
    start = clock();
    d = BF(g5, 0);
    stop = clock();
    cout << "The average time: " << double(stop-start)/double(1000) << "ms" << endl;
    delete d;
    return 0;
}